/**
 * \file ReseauAerien.cpp
 * \brief Implémentattion de la classe ReseauAerien.
 * \author Pierre-Marc Levasseur, Simon Rodier
 * \version 0.1
 * \date juillet 2014
 *
 *  Travail pratique numéro 3
 *
 */

#include "ReseauAerien.h"
#include<algorithm>
#include<queue>
#include<stack>

using namespace std;

namespace TP3
{

	/**
	 *  \fn ReseauAerien::ReseauAerien(const ReseauAerien &source)
	 *  \param[in] source: un réseau aérien
	 */
	ReseauAerien::ReseauAerien(const ReseauAerien &source)
	{
		try
		{
			nomReseau = source.nomReseau;
			unReseau = source.unReseau;
		}
		catch (bad_alloc& ba)
		{
			throw ba;
		}
	}

	/**
	 *  \fn ReseauAerien::operator=(const ReseauAerien& src)
	 *  \param[in] src: un ReseauAerien à copier
	 *  \return un ReseauAerien qui est copie profonde de src
	 */
	ReseauAerien& ReseauAerien::operator=(const ReseauAerien& src)
	{
		try
		{
			//si l'addresse de l'objet courant est égale à l'addresse de src (même objet), on ne fait rien
			if (this == &src)
				return *this;
			nomReseau = src.nomReseau;
			unReseau = src.unReseau;
			return *this;
		}
		catch (bad_alloc& ba)
		{
			throw ba;
		}
	}


	/**
	 *  \fn ReseauAerien::viderReseau()
	 *  \param[out] le réseau aerien est vide /réinitialisé
	 */
	void ReseauAerien::viderReseau()
	{
		nomReseau.clear();
		unReseau.detruireGraphe();
	}

	/**
	 * \fn ReseauAerien::ChargerReseau
	 *
	 * \param [in] f: fichier ouvert dans lequel on fait la lecture
	 */
	void ReseauAerien::chargerReseau(ifstream& f)
	{
		if(!f.is_open())
			throw logic_error("chargerReseau: le fichier envoyé n'est pas ouvert correctement");

		// On va chercher le nom du réseau
		string ligne;
		getline(f, ligne);
		string::iterator it = find(ligne.begin(), ligne.end(), ' '); // premier espace
		it++;
		it = find(it, ligne.end(), ' '); // deuxième espace
		it++; // pour qu'il pointe sur le premier caractère du nom du réseau
		nomReseau = string(it, ligne.end());

		// On va chercher le nombre de villes
		int nbVilles = 0;
		f >> nbVilles;
		f.ignore();
		getline(f, ligne); // pour ignorer le reste de la ligne

		// On va chercher le nombre de trajets
		int nbTrajets = 0;
		f >> nbTrajets;
		f.ignore();
		getline(f,ligne); // pour ignorer le reste de la ligne
		getline(f,ligne); // pour ignorer la ligne "Liste des villes:"

		// On va chercher toutes les villes
		for(int i = 0; i < nbVilles; i++)
		{
			getline(f, ligne);
			string nomVille = ligne;
			float lt, lg;
			f >> lt;
			f >> lg;

			unReseau.ajouterSommet(nomVille, lt, lg);
			f.ignore();
		}

		getline(f,ligne); // pour ignorer la ligne "Liste des trajets:"

		// On va chercher tous les trajets
		for(int i = 0; i < nbTrajets; i++)
		{
			f >> ligne;
			string villeDepart = ligne;
			f >> ligne;
			string villeDestination = ligne;

			float duree;
			f >> duree;
			float cout;
			f >> cout;
			int ns;
			f >> ns;

			unReseau.ajouterArc(villeDepart, villeDestination, duree, cout, ns);
		}
	}



	/**
	 *  \fn ReseauAerien::sauvegarderReseau(std::ofstream & SortieFichier)
	 *  \param[in] SortieFichier: fichier où qu'on enregistra les données
	 *  \param[out] SortieFichier contient les données du réseau aérien
	 */
	void ReseauAerien::sauvegarderReseau(std::ofstream & SortieFichier) const
	{
		if (!SortieFichier.is_open())
			throw logic_error("sauvegarderReseau: le fichier n'est pas ouvert correctement.");
		//il faut tout mettre dans SortieFichier... ex:  SortieFichier<< blabla
		//******ENTETE DU FICHIER
		//Nom Réseau: ________
		SortieFichier<<"Reseau Aerien: "<<nomReseau<<endl;
		//__ villes
		SortieFichier<<unReseau.nombreSommets()<<" villes"<<endl;
		//__ trajets
		SortieFichier<<unReseau.getNombreArcs()<<" trajets"<<endl;
		//******LISTE DES VILLES
		SortieFichier<<"Liste des villes:"<<endl;
		//il faut sortir les villes une par une avec leur lt et lg
		//Nom_De_Ville
		//lt lg
		//on obtient en commencant un vecteur avec toutes les villes
		vector<string> villes = unReseau.listerNomsSommets();
		for(vector<string>::iterator itVilles=villes.begin(); itVilles!=villes.end(); itVilles++)
		{
			SortieFichier<<*itVilles<<endl;
			Coordonnees coordVille = unReseau.getCoordonneesSommet(*itVilles);
			SortieFichier<<coordVille.lt<<" "<<coordVille.lg<<endl;
		}
		//******LISTE DES TRAJETS
		SortieFichier<<"Liste des trajets:"<<endl;
		//Ville_A
		//Ville_B
		//Duree Cout NiveauSecurité

		//on boucle dans les villes,
		for(vector<string>::iterator itTrajets=villes.begin(); itTrajets!=villes.end(); itTrajets++)
		{
			//on obtient tous les destinations possibles
			vector<string> destinations = unReseau.listerSommetsAdjacents(*itTrajets);
			//et pour chaque destination, on imprime les infos nécessaires
			for (vector<string>::iterator itDest=destinations.begin(); itDest!=destinations.end(); itDest++)
			{
				SortieFichier<<*itTrajets<<endl;
				SortieFichier<<*itDest<<endl;
				Ponderations ponderTrajet = unReseau.getPonderationsArc(*itTrajets, *itDest);
				SortieFichier<<ponderTrajet.duree<<" "<<ponderTrajet.cout<<" "<<ponderTrajet.ns<<endl;
			}
		}
	}
	
		/**
	 * \fn ReseauAerien::fermetureReseau()
	 *
	 * \return renvoie un nouveau réseau aérien qui correspond à la fermeture transitive du réseau courant
	 */
	ReseauAerien ReseauAerien::fermetureReseau()
	{
		ReseauAerien copie = *this;
		Graphe* grapheCopie = &(copie.unReseau);

		vector<string> sommets = grapheCopie->listerNomsSommets();

		for(size_t k = 0; k < sommets.size(); k++)
			for(size_t i = 0; i < sommets.size(); i++)
				for(size_t j = 0; j < sommets.size(); j++)
					if(!grapheCopie->arcExiste(sommets[i], sommets[j]) &&
							(grapheCopie->arcExiste(sommets[i], sommets[k]) && grapheCopie->arcExiste(sommets[k], sommets[j])))
						grapheCopie->ajouterArc(sommets[i], sommets[j], 0,0,0);
		return copie;
	}

		/**
		 *  \fn ReseauAerien::rechercheCheminDijkstra(const std::string& origine, const std::string& destination, bool dureeCout)
		 *  \param[in] origine: la ville de départ
		 *  \param[in] destination: la ville de destination
		 *  \param[in] dureeCout: vrai = utiliser durée de vol comme pondération sur les trajets; faux = utiliser le cout comme pondération
		 *  \return un chemin avec les détails du meilleur chemin selon les paramètres choisi, ou la valeur reussi a false s'il n'y a pas de chemin possible
		 */
		Chemin ReseauAerien::rechercheCheminDijkstra(const std::string& origine, const std::string& destination, bool dureeCout)
		{
			if (!unReseau.sommetExiste(origine) || !unReseau.sommetExiste(destination))
				throw logic_error("rechercheCheminDijkstra: une des villes demandées ne fait pas partie du réseau.");
			map<string, DonneesVilleDijkstra> villesDuReseau;
			typedef map<string, DonneesVilleDijkstra>::iterator villeIter;
			vector<string> villesInitialisation = unReseau.listerNomsSommets();
			//PHASE INITIALISATION
			//on initialise tous les ponderations à 0 et tous les sommets ne sont pas visité
			for(size_t i = 0 ; i < villesInitialisation.size() ; i++)
			{
				DonneesVilleDijkstra donneesVilleCourante;
				donneesVilleCourante.origine = "", donneesVilleCourante.ponder=infinie, donneesVilleCourante.visite=false;
				villesDuReseau[villesInitialisation[i]] = donneesVilleCourante;
			}
			//on change la ponderation du sommet d'origine à 0
			villesDuReseau.find(origine)->second.ponder = 0;

			//RELACHEMENT
			for (unsigned int nbSommetsATraiter = 0; nbSommetsATraiter < villesDuReseau.size(); nbSommetsATraiter++)
			{
				float minCourant = infinie;
				string nomSommetMin;
				villeIter villeCourante=villesDuReseau.end();		//la ville qu'on va traiter
				//trouver le sommet de plus petite valeur qui n'est pas traité
				for(villeIter itTrouveMin = villesDuReseau.begin(); itTrouveMin != villesDuReseau.end(); itTrouveMin++)
				{
					if(itTrouveMin->second.ponder < minCourant && itTrouveMin->second.visite == false)
					{
						minCourant = itTrouveMin->second.ponder;
						villeCourante = itTrouveMin;
					}
				}
				//si on se rend ici et que villeCourante==villesDuReseau.end(), c'est que tous les sommets sont à INFINIE.
				//on prend donc la premiere ville non-visitée
				if(villeCourante==villesDuReseau.end())
					for(villeIter itPrendreVille=villesDuReseau.begin(); itPrendreVille!=villesDuReseau.end(); itPrendreVille++)
						if(itPrendreVille->second.visite==false)
						{
							villeCourante= itPrendreVille;
							break;
						}
				//on indique que le sommet est parcourue
				villeCourante->second.visite=true;
				//on a donc un sommet de moins à traiter
				//pour tous les sommets adjacents à la ville courante
				vector<string> destinationsPossibles = unReseau.listerSommetsAdjacents(villeCourante->first);
				for (vector<string>::iterator itDest = destinationsPossibles.begin(); itDest!=destinationsPossibles.end(); itDest++)
				{
					//allons chercher la ponderation de l'arc
					float ponderArc;
					if(dureeCout)
						ponderArc = unReseau.getPonderationsArc(villeCourante->first, *itDest).duree;
					else
						ponderArc = unReseau.getPonderationsArc(villeCourante->first, *itDest).cout;
					//si villeCourante.ponder + arc.ponder < destination.ponder
					_relachement(villeCourante->first, *itDest, ponderArc, villesDuReseau);
				}
			}

			//on a maintenant tous les données nécessaires pour construire le chemin
			//villeIter villeAPlacer = villesDuReseau.find(destination);
			Chemin reponse;
			reponse.coutTotal=0, reponse.dureeTotale=0, reponse.nsTotal=0, reponse.reussi=false;

			_preparerChemin(reponse, origine, destination, villesDuReseau);
			return reponse;
		}

		/**
		 * \fn ReseauAerien::_preparerChemin(Chemin&, const string&, const string&, map<std::string, DonneesVilleDijkstra>&)
		 *
		 * \param [in] origine: nom de la ville de départ
		 * \param [in] destination: nom de la ville d'arrivée
		 * \param [in] mapVille: map dont la clé est le nom d'une ville et contenant la ville précédente et la pondération
		 *
		 * \param [out] reponse: Chemin& dans lequel on construit le chemin pour aller de origine à destination
		 */
		void ReseauAerien::_preparerChemin(Chemin& reponse, const std::string& origine, const std::string& destination, std::map<std::string, DonneesVilleDijkstra>& mapVille)
		{

			map<string, DonneesVilleDijkstra>::iterator villeAPlacer = mapVille.find(destination);

			if(mapVille[destination].origine == "")
				return;
			while(!reponse.reussi)
			{
				if(villeAPlacer->second.origine == "")
					return;
				Ponderations ponderCourant = unReseau.getPonderationsArc(villeAPlacer->second.origine, villeAPlacer->first);
				reponse.coutTotal += ponderCourant.cout;
				reponse.dureeTotale += ponderCourant.duree;
				if(villeAPlacer->second.origine==origine)
				{
					reponse.reussi = true;
				}
				else
					reponse.dureeTotale++;		//1 heure pour l'escale
				reponse.nsTotal += ponderCourant.ns;
				reponse.listeVilles.push_back(villeAPlacer->first);
				villeAPlacer = mapVille.find(villeAPlacer->second.origine);
			}
			reponse.listeVilles.push_back(origine);
			reverse (reponse.listeVilles.begin(), reponse.listeVilles.end());
		}

		/**
		 * \fn ReseauAerien::_relachement(string&, string&, float)
		 *
		 * \param [in] sommetA: sommet d'origine
		 * \param [in] sommetB: sommet qu'on vérifie
		 * \param [in] cout: cout de l'arc entre sommetA et sommetB
		 *
		 * \return true si on fait un changement, false sinon
		 */
		bool ReseauAerien::_relachement(const string& sommetA, const string& sommetB, float coutArc, map<string, DonneesVilleDijkstra>& mapVille)
		{
			if(mapVille[sommetB].ponder-(mapVille[sommetA].ponder + coutArc) > epsilon)
			{
				//si villeCourante.ponder + arc.ponder < destination.ponder
				//destination.ponder = villeCourante.ponder + arc.ponder
				mapVille[sommetB].ponder = mapVille[sommetA].ponder + coutArc;
				//et la nouvelle origine de la destination est la ville courante
				mapVille[sommetB].origine = sommetA;
				return true;
			}
			return false;
		}




		/**
		 *  \fn ReseauAerien::bellManFord(const std::string& origine, const std::string& destination, int dureeCoutNiveau)
		 *  \param[in] origine: la ville d'origine
		 *  \param[in] destination: la ville de destination
		 *  \param[in] dureeCoutNiveau: indique la ponderation a utiliser. 1: duree, 2: cout, 3: niveau securité
		 *  \return le chemin avec la plus faible pondération selon le dureeCoutNiveau choisit
		 */
		Chemin ReseauAerien::bellManFord(const std::string& origine, const std::string& destination, int dureeCoutNiveau)
		{
			//INITIALISATION
			if (!unReseau.sommetExiste(origine) || !unReseau.sommetExiste(destination))
				throw logic_error("bellManFord: une des villes demandées ne fait pas partie du réseau.");
			map<string, DonneesVilleDijkstra> villesDuReseau;
			typedef map<string, DonneesVilleDijkstra>::iterator villeIter;
			vector<string> villesInitialisation = unReseau.listerNomsSommets();
			//PHASE INITIALISATION
			//on initialise tous les ponderations à 0 et tous les sommets ne sont pas visité
			for(size_t i = 0 ; i < villesInitialisation.size() ; i++)
			{
				DonneesVilleDijkstra donneesVilleCourante;
				donneesVilleCourante.origine = "", donneesVilleCourante.ponder=infinie, donneesVilleCourante.visite=false;
				villesDuReseau[villesInitialisation[i]] = donneesVilleCourante;
			}
			//on change la ponderation du sommet d'origine à 0
			villesDuReseau.find(origine)->second.ponder = 0;

			//RELACHEMENTS
			for (size_t i = 0 ; i<(villesDuReseau.size()-1) ; i++)
			{
				//pour tous les sommets du graphe,
				for(villeIter vIt = villesDuReseau.begin(); vIt!=villesDuReseau.end(); vIt++)
				{
					//on visite tous les arcs
					vector<string> destinationsDeCeSommet = unReseau.listerSommetsAdjacents(vIt->first);
					for(vector<string>::iterator destIt=destinationsDeCeSommet.begin(); destIt!=destinationsDeCeSommet.end(); destIt++)
					{
						Ponderations ponder = unReseau.getPonderationsArc(vIt->first, *destIt);
						float ponderArc=0;
						if(dureeCoutNiveau==1)
							ponderArc=ponder.duree;
						else if (dureeCoutNiveau==2)
							ponderArc=ponder.cout;
						else if (dureeCoutNiveau==3)
							ponderArc=ponder.ns;
						//si ponderSommetDest > ponderSommetOrigine + ponderArc, il faut changer les valeurs de ponderSommetDest
						_relachement(vIt->first, *destIt, ponderArc, villesDuReseau);
					}
				}
			}

			Chemin reponse;
			reponse.coutTotal=0, reponse.dureeTotale=0, reponse.nsTotal=0, reponse.reussi=false;

			//VERIF CYCLES NÉGATIFS
			//pour tous les sommets du graphe,
			for(villeIter vIt = villesDuReseau.begin(); vIt!=villesDuReseau.end(); vIt++)
			{
				//on visite tous les arcs
				vector<string> destinationsDeCeSommet = unReseau.listerSommetsAdjacents(vIt->first);
				for(vector<string>::iterator destIt=destinationsDeCeSommet.begin(); destIt!=destinationsDeCeSommet.end(); destIt++)
				{
					Ponderations ponder = unReseau.getPonderationsArc(vIt->first, *destIt);
					float ponderArc=0;
					if(dureeCoutNiveau==1)
						ponderArc=ponder.duree;
					else if (dureeCoutNiveau==2)
						ponderArc=ponder.cout;
					else if (dureeCoutNiveau==3)
						ponderArc=ponder.ns;
					//si ponderSommetDest > ponderSommetOrigine + ponderArc, il existe un cycle négatif
					if (villesDuReseau[*destIt].ponder - (villesDuReseau[vIt->first].ponder + ponderArc) > epsilon)
						return reponse;
				}
			}
			//PREPARER CHEMIN
			_preparerChemin(reponse, origine, destination, villesDuReseau);
			return reponse;
		}

	/**
	 * \fn ReseauAerien::rechercheCheminLargeur(const string&, const string&)
	 *
	 * \param [in] origine: ville de départ
	 * \param [in] destination: ville d'arrivée vers laquelle on cherche un chemin
	 *
	 * \return vector<string> contenant le nom des villes qu'on doit parcourir faire le trajet de la ville origine à la ville destination
	 */
	vector<string> ReseauAerien::rechercheCheminLargeur(const string& origine, const string& destination)
	{
		if(!unReseau.sommetExiste(origine) || !unReseau.sommetExiste(destination))
			throw logic_error("rechercheCheminLargeur: l'une des villes passées en arguement ne fait pas partie du réseau");

		unReseau.setSommetsFalse();

		// va contenir le nom d'une ville comme clé et le nom de la ville précédante pour atteindre origine comme valeur
		map<string, string> villePrecedente;
		queue<string> q;
		q.push(origine);
		unReseau.setSommetEtat(origine, true);

		while(!q.empty())
		{
			string ville = q.front();
			q.pop();

			vector<string> villeAdjacentes;
			villeAdjacentes = unReseau.listerSommetsAdjacents(ville);
			for(size_t i = 0; i < villeAdjacentes.size(); i++)
			{
				// si la ville n'est pas parcourue
				if(!unReseau.getSommetEtat(villeAdjacentes[i]))
				{
					q.push(villeAdjacentes[i]);
					unReseau.setSommetEtat(villeAdjacentes[i], true); // on la marque comme parcourue
					villePrecedente[villeAdjacentes[i]] = ville; // on met la ville courrante comme ville précédante
				}
			}
		}
		// on construit le chemin
		vector<string> chemin;
		if(villePrecedente[destination] == "")
			return chemin;
		chemin.push_back(destination);
		string ville = destination;
		while(villePrecedente[ville] != origine)
		{
			if(villePrecedente[ville] == "")
			{
				chemin.clear();
				return chemin;
			}
			chemin.push_back(villePrecedente[ville]);
			ville = villePrecedente[ville];
		}
		chemin.push_back(origine);
		reverse(chemin.begin(), chemin.end()); // le chemin est à l'envers donc on fait un reverse
		return chemin;
	}

	/**
	 * \fn ReseauAerien::algorithmeAstar(const string&, const string&, bool)
	 *
	 * \param [in] origine: ville de départ
	 * \param [in] destination: ville d'arrivée vers laquelle on cherche un chemin
	 * \param [in] dureeCout: booléen qui permet de choisir la pondération qu'on va utiliser pour trouver le chemin
	 *
	 * \return renvoie un chemin pour aller de la ville origine à la ville destination selon la pondération choisit
	 */
	Chemin ReseauAerien::algorithmeAstar(const string& origine, const string& destination, bool dureeCout)
	{
		if(!unReseau.sommetExiste(origine) || !unReseau.sommetExiste(destination))
					throw logic_error("algorithmeAstar: l'une des villes passées en arguement ne fait pas partie du réseau");

		unReseau.setSommetsFalse();
		map<string, DonneesVilleDijkstra> sommetsAVisiter;
		map<string, DonneesVilleDijkstra> sommetsVisite;
		typedef map<string, DonneesVilleDijkstra>::iterator mapIter;
		sommetsAVisiter[origine].ponder = unReseau.getDistance(origine, destination);
		while(!sommetsAVisiter.empty())
		{
			float coutmin = infinie; // va contenir le coût pour aller à la prochaine ville
			string villeCourante; // va contenir la ville qu'on explore
			// on choisit la prochaine ville selon son coût
			for(mapIter it = sommetsAVisiter.begin(); it != sommetsAVisiter.end(); it++)
			{
				if(it->second.ponder < coutmin)
				{
					villeCourante = it->first;
					coutmin = it->second.ponder;
				}
			}
			// on marque la ville comme parcourue
			unReseau.setSommetEtat(villeCourante, true);
			sommetsVisite[villeCourante] = sommetsAVisiter[villeCourante];
			// on l'enlève de la liste des villes à visiter
			sommetsAVisiter.erase(villeCourante);
			// on va chercher toutes les villes adjacentes à la ville courante
			vector<string> villeAdj = unReseau.listerSommetsAdjacents(villeCourante);
			for(size_t i = 0; i < villeAdj.size(); i++)
			{
				if(!unReseau.getSommetEtat(villeAdj[i])) // si la ville n'a pas été visitée
				{
					// on calcul le coût pour aller à la ville adjacente
					float cout = unReseau.getDistance(villeCourante, villeAdj[i]);
					Ponderations temp = unReseau.getPonderationsArc(villeCourante, villeAdj[i]);
					cout += (dureeCout ? temp.duree : temp.cout);
					cout += unReseau.getDistance(villeAdj[i], destination);
					// on vérifie si la ville est déjà dans la liste des villes à visiter
					mapIter it = sommetsAVisiter.find(villeAdj[i]);
					if(it != sommetsAVisiter.end()) // si elle est dans la liste
					{
						if(it->second.ponder > cout) // et que ça coûte moins cher de passer par la ville courante
						{
							it->second.ponder = cout;
							it->second.origine = villeCourante;
						}
					}
					else // sinon on l'ajoute
					{
						sommetsAVisiter[villeAdj[i]].ponder = cout;
						sommetsAVisiter[villeAdj[i]].origine = villeCourante;
					}
				}
			}
			mapIter it = sommetsAVisiter.find(destination);
			if(it != sommetsAVisiter.end()) // on vérifie si la destination est dans la liste des villes à visiter
			{
				sommetsVisite[destination] = sommetsAVisiter[destination];
				break;
			}
		}
		// on vérifie que la ville de destination fait partie de la liste des sommets à visiter
		mapIter it = sommetsAVisiter.find(destination);
		if(it == sommetsAVisiter.end()) // si elle n'est pas là, on retourne un chemin vide
		{
			Chemin retour;
			retour.reussi = false;
			return retour;
		}
		// on reconstruit le chemin entre la ville origine et la ville destination
		Chemin retour;
		retour.coutTotal = 0.0; retour.dureeTotale = 0.0; retour.nsTotal = 0;
		_preparerChemin(retour, origine, destination, sommetsVisite);
		return retour;
	}

	/**
	 *  \fn ReseauAerien::getNomReseau()
	 *  \return le nom du reseauAerien
	 */
	std::string ReseauAerien::getNomReseau() const
	{
		return nomReseau;
	}

	/**
	 *  \brief retourne la taille du reseau aerien (nombre de villes)
	 */
	/**
	 *  \fn ReseauAerien::getTailleReseau()
	 *  \return le nombre de villes dans le reseau
	 */
	int ReseauAerien::getTailleReseau() const
	{
		return unReseau.nombreSommets();
	}
} //Fin du namespace
